// ===============================================================================
// Authors: AFRL/RQQD
// Organization: Air Force Research Laboratory, Aerospace Systems Directorate, Power and Control Division
// 
// Copyright (c) 2017 Government of the United State of America, as represented by
// the Secretary of the Air Force.  No copyright is claimed in the United States under
// Title 17, U.S. Code.  All Other Rights Reserved.
// ===============================================================================

/*
 * GRAL: GRAphing Library for Java(R)
 *
 * (C) Copyright 2009-2013 Erich Seifert <dev[at]erichseifert.de>,
 * Michael Seifert <mseifert[at]error-reports.org>
 *
 * This file is part of GRAL.
 *
 * GRAL is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * GRAL is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with GRAL.  If not, see <http://www.gnu.org/licenses/>.
 */
package de.erichseifert.gral.util;

import java.awt.BasicStroke;
import java.awt.Shape;
import java.awt.Stroke;
import java.awt.geom.AffineTransform;
import java.awt.geom.Area;
import java.awt.geom.FlatteningPathIterator;
import java.awt.geom.Line2D;
import java.awt.geom.Path2D;
import java.awt.geom.PathIterator;
import java.awt.geom.Point2D;
import java.io.Serializable;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

/**
 * Abstract class that represents a collection of utility functions
 * concerning geometry.
 */
public abstract class GeometryUtils {
	/** Precision. */
	public static final double EPSILON = 1e-5;
	/** Precision squared. */
	public static final double EPSILON_SQ = EPSILON*EPSILON;

	/**
	 * Default constructor that prevents creation of class.
	 */
	private GeometryUtils() {
		throw new UnsupportedOperationException();
	}

	/**
	 * Returns the line fragments of the specified Shape.
	 * @param path Shape to be divided.
	 * @param swapped Invert segment direction.
	 * @return Array of lines.
	 */
	public static Line2D[] shapeToLines(Shape path, boolean swapped) {
		Deque<Line2D> lines = new ArrayDeque<Line2D>();
		PathIterator i =
			new FlatteningPathIterator(path.getPathIterator(null), 0.5);

		double[] coords = new double[6];
		double[] coordsPrev = new double[6];
		while (!i.isDone()) {
			int segment = i.currentSegment(coords);

			if (segment == PathIterator.SEG_LINETO ||
					segment == PathIterator.SEG_CLOSE) {
				Line2D line;
				if (!swapped) {
					line = new Line2D.Double(
						coordsPrev[0], coordsPrev[1], coords[0], coords[1]);
					lines.addLast(line);
				} else {
					line = new Line2D.Double(
						coords[0], coords[1], coordsPrev[0], coordsPrev[1]);
					lines.addFirst(line);
				}
			}
			if (segment == PathIterator.SEG_CLOSE && !lines.isEmpty()) {
				Point2D firstPoint = lines.getFirst().getP1();
				Point2D lastPoint = lines.getLast().getP2();
				if (!firstPoint.equals(lastPoint)) {
					Line2D line;
					if (!swapped) {
						line = new Line2D.Double(
							coords[0], coords[1], firstPoint.getX(), firstPoint.getY());
						lines.addLast(line);
					} else {
						line = new Line2D.Double(
							firstPoint.getX(), firstPoint.getY(), coords[0], coords[1]);
						lines.addFirst(line);
					}
				}
			}

			System.arraycopy(coords, 0, coordsPrev, 0, 6);
			i.next();
		}
		Line2D[] linesArray = new Line2D[lines.size()];
		lines.toArray(linesArray);
		return linesArray;
	}

	/**
     * Returns all intersection points of two shapes.
     * @param s1 First shape
     * @param s2 Second shape
     * @return Intersection points, or empty array if
     * no intersections were found
     */
    public static List<Point2D> intersection(final Shape s1, final Shape s2) {
    	List<Point2D> intersections = new ArrayList<Point2D>(2);
    	Line2D[] lines1 = shapeToLines(s1, false);
    	Line2D[] lines2 = shapeToLines(s2, false);

    	for (Line2D l1 : lines1) {
			for (Line2D l2 : lines2) {
				Point2D intersection = intersection(l1, l2);
				if (intersection != null) {
					intersections.add(intersection);
				}
			}
		}

    	return intersections;
	}

    /**
     * Returns the intersection point of two lines.
     * @param l1 First line
     * @param l2 Second line
     * @return Intersection point, or {@code null} if
     * no intersection was found
     */
    public static Point2D intersection(final Line2D l1, final Line2D l2) {
    	Point2D p0 = l1.getP1();
		Point2D d0 = new Point2D.Double(l1.getX2() - p0.getX(), l1.getY2() - p0.getY());
		Point2D p1 = l2.getP1();
		Point2D d1 = new Point2D.Double(l2.getX2() - p1.getX(), l2.getY2() - p1.getY());

		Point2D e = new Point2D.Double(p1.getX() - p0.getX(), p1.getY() - p0.getY());
		double kross = d0.getX()*d1.getY() - d0.getY()*d1.getX();
		double sqrKross = kross*kross;
		double sqrLen0 = d0.distanceSq(0.0, 0.0);
		double sqrLen1 = d1.distanceSq(0.0, 0.0);

		if (sqrKross > EPSILON_SQ * sqrLen0 * sqrLen1) {
			double s = (e.getX()*d1.getY() - e.getY()*d1.getX())/kross;
			if (s < 0d || s > 1d) {
				return null;
			}
			double t = (e.getX()*d0.getY() - e.getY()*d0.getX())/kross;
			if (t < 0d || t > 1d) {
				return null;
			}
			return new Point2D.Double(
				p0.getX() + s*d0.getX(), p0.getY() + s*d0.getY()
			);
		}

		/*
		double sqrLenE = e.lengthSq();
		kross = e.cross(d0);
		sqrKross = kross*kross;
		if (sqrKross > EPSILON_SQ*sqrLen0*sqrLenE) {
			return null;
		}
		*/

		return null;
	}

    /**
     * Expand or shrink a shape in all directions by a defined offset.
     * @param s Shape
     * @param offset Offset
     * @return New shape that was expanded or shrunk by the specified amount
     */
    public static Area grow(final Shape s, final double offset) {
    	return grow(s, offset, BasicStroke.JOIN_MITER, 10f);
    }

    /**
     * Expand or shrink a shape in all directions by a defined offset.
     * @param s Shape
     * @param offset Offset to expand/shrink
     * @param join Method for handling edges (see BasicStroke)
     * @param miterlimit Limit for miter joining method
     * @return New shape that is expanded or shrunk by the specified amount
     */
    public static Area grow(final Shape s, final double offset, int join,
    		float miterlimit) {
    	Area shape = new Area(s);

    	if (MathUtils.almostEqual(offset, 0.0, EPSILON)) {
    		return shape;
    	}

    	Stroke stroke = new BasicStroke((float)Math.abs(2.0*offset),
    			BasicStroke.CAP_SQUARE, join, miterlimit);
    	Area strokeShape = new Area(stroke.createStrokedShape(s));

    	if (offset > 0.0) {
    		shape.add(strokeShape);
    	} else {
    		shape.subtract(strokeShape);
    	}

    	return shape;
    }

    /**
     * Subtract a specified geometric area of data points from another shape to yield gaps.
     * @param shapeArea Shape from which to subtract.
     * @param gap Size of the gap.
     * @param rounded Gap corners will be rounded if {@code true}.
     * @param pointPos Position of the data point
     * @param pointShape Shape of the data point
     * @return Shape with punched holes
     */
    public static Area punch(Area shapeArea, double gap, boolean rounded,
    		Point2D pointPos, Shape pointShape) {
		if (gap <= 1e-10 || pointPos == null || pointShape == null) {
			return shapeArea;
		}

		AffineTransform tx = AffineTransform.getTranslateInstance(
			pointPos.getX(), pointPos.getY());

		int gapJoin = rounded ? BasicStroke.JOIN_ROUND : BasicStroke.JOIN_MITER;
		Area gapArea = GeometryUtils.grow(
			tx.createTransformedShape(pointShape), gap, gapJoin, 10f);

		shapeArea.subtract(gapArea);

		return shapeArea;
    }

    /**
     * Utility data class for the values of the segments in a geometric shape.
     */
    public static final class PathSegment implements Serializable {
    	/** Version id for serialization. */
		private static final long serialVersionUID = 526444553637955799L;

		/** Segment type id as defined in {@link PathIterator}. */
    	public final int type;
    	/** Starting point. */
    	public final Point2D start;
    	/** End point. */
    	public final Point2D end;
    	/** Coordinates necessary to draw the segment. */
    	public final double[] coords;

    	/**
    	 * Initializes a new instance with type, starting and end point, and
    	 * all other coordinates that are necessary to draw the segment.
    	 * @param type Segment type id as defined in {@link PathIterator}.
    	 * @param start Starting point.
    	 * @param end End point.
    	 * @param coords Array of coordinates necessary to draw the segment.
    	 */
    	public PathSegment(int type, Point2D start, Point2D end, double[] coords) {
			this.type = type;
			this.start = start;
			this.end = end;
			this.coords = new double[6];
			System.arraycopy(coords, 0, this.coords, 0, 6);
		}
    }

    /**
     * Returns a list of a shape's segments as they are returned by its path
     * iterator.
     * @param shape Shape to be iterated.
     * @return A list of path segment objects.
     */
    public static List<PathSegment> getSegments(Shape shape) {
    	PathIterator path =  shape.getPathIterator(null);

    	Point2D pointStart = null, pointEnd = null;
		double[] coords = new double[6];
		List<PathSegment> segments = new LinkedList<PathSegment>();
		while (!path.isDone()) {
			int type = path.currentSegment(coords);

			if (type == PathIterator.SEG_MOVETO || type == PathIterator.SEG_LINETO) {
				pointEnd = new Point2D.Double(coords[0], coords[1]);
			} else if (type == PathIterator.SEG_QUADTO) {
				pointEnd = new Point2D.Double(coords[2], coords[3]);
			} else if (type == PathIterator.SEG_CUBICTO) {
				pointEnd = new Point2D.Double(coords[4], coords[5]);
			}

			PathSegment segment = new PathSegment(type, pointStart, pointEnd, coords);
			segments.add(segment);

			pointStart = pointEnd;
			path.next();
		}

		return segments;
    }

    /**
     * Constructs a geometric shape from a list of path segments.
     * @param segments List of path segments.
     * @param isDouble {@code true} if the shape contents should be stored with
     *        double values, {@code false} if they should be stored as float.
     * @return A geometric shape.
     */
    public static Shape getShape(List<PathSegment> segments, boolean isDouble) {
    	if (isDouble) {
    		return getShapeDouble(segments);
    	} else {
    		return getShapeFloat(segments);
    	}
    }

    /**
     * Constructs a geometric shape with double precision from a list of path
     * segments.
     * @param segments List of path segments.
     * @return A geometric shape.
     */
    private static Shape getShapeDouble(List<PathSegment> segments) {
		Path2D.Double path =
			new Path2D.Double(Path2D.WIND_NON_ZERO, segments.size());
		for (PathSegment segment : segments) {
			double[] coords = segment.coords;
			if (segment.type == PathIterator.SEG_MOVETO) {
				path.moveTo(coords[0], coords[1]);
			} else if (segment.type == PathIterator.SEG_LINETO) {
				path.lineTo(coords[0], coords[1]);
			} else if (segment.type == PathIterator.SEG_QUADTO) {
				path.quadTo(coords[0], coords[1],
					coords[2], coords[3]);
			} else if (segment.type == PathIterator.SEG_CUBICTO) {
				path.curveTo(coords[0], coords[1],
					coords[2], coords[3],
					coords[4], coords[5]);
			} else if (segment.type == PathIterator.SEG_CLOSE) {
				path.closePath();
			}
		}
		return path;
	}

    /**
     * Constructs a geometric shape with single precision from a list of path
     * segments.
     * @param segments List of path segments.
     * @return A geometric shape.
     */
	private static Shape getShapeFloat(List<PathSegment> segments) {
		Path2D.Float path =
			new Path2D.Float(Path2D.WIND_NON_ZERO, segments.size());
		for (PathSegment segment : segments) {
			float[] coords = new float[segment.coords.length];
			for (int i = 0; i < coords.length; i++) {
				coords[i] = (float) segment.coords[i];
			}
			if (segment.type == PathIterator.SEG_MOVETO) {
				path.moveTo(coords[0], coords[1]);
			} else if (segment.type == PathIterator.SEG_LINETO) {
				path.lineTo(coords[0], coords[1]);
			} else if (segment.type == PathIterator.SEG_QUADTO) {
				path.quadTo(coords[0], coords[1],
					coords[2], coords[3]);
			} else if (segment.type == PathIterator.SEG_CUBICTO) {
				path.curveTo(coords[0], coords[1],
					coords[2], coords[3],
					coords[4], coords[5]);
			} else if (segment.type == PathIterator.SEG_CLOSE) {
				path.closePath();
			}
		}
		return path;
	}

	/**
     * Returns a clone of a specified shape which  has a reversed order of the
     * points, lines and curves.
     * @param shape Original shape.
     * @return Shape with reversed direction.
     */
    public static Shape reverse(Shape shape) {
    	List<PathSegment> segments = getSegments(shape);

		boolean closed = false;
		Path2D reversed =
			new Path2D.Double(Path2D.WIND_NON_ZERO, segments.size());
		ListIterator<PathSegment> i = segments.listIterator(segments.size());
		while (i.hasPrevious()) {
			PathSegment segment = i.previous();

			if (segment.type == PathIterator.SEG_CLOSE) {
				closed = true;
				continue;
			}

			if (reversed.getCurrentPoint() == null) {
				reversed.moveTo(
					segment.end.getX(), segment.end.getY());
			}
			if (segment.type == PathIterator.SEG_LINETO) {
				reversed.lineTo(
					segment.start.getX(), segment.start.getY());
			} else if (segment.type == PathIterator.SEG_QUADTO) {
				reversed.quadTo(
					segment.coords[0], segment.coords[1],
					segment.start.getX(), segment.start.getY());
			} else if (segment.type == PathIterator.SEG_CUBICTO) {
				reversed.curveTo(
					segment.coords[2], segment.coords[3],
					segment.coords[0], segment.coords[1],
					segment.start.getX(), segment.start.getY());
			} else if (segment.type == PathIterator.SEG_MOVETO) {
				if (closed) {
					reversed.closePath();
					closed = false;
				}
			}
		}

		return reversed;
    }
}
